package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2016年12月29日
*时间：上午9:59:06
*/
public class Q61 {
    /** 
     *@param A : an integer sorted array
     *@param target :  an integer to be inserted
     *return : a list of length 2, [index1, index2]
     */
    public int[] searchRange(int[] A, int target) {
        int[] rs = new int[2];
        rs[0] = searchMinOrMax(A, 0, A.length - 1, target, true);
        rs[1] = searchMinOrMax(A, 0, A.length - 1, target, false);
        return rs;
    }

    private int searchMinOrMax(int[] A, int left, int right, int target, boolean isMin) {
        int k = -1;
        while (left <= right) {
            int point = (left + right) / 2;
            if (A[point] > target) {
                right = point - 1;
            } else if (A[point] == target) {
                if (isMin) {
                    right = point - 1;
                } else {
                    left = point + 1;
                }
                k = point;
            } else {
                left = point + 1;
            }
        }
        return k;
    }

    @Test
    public void testA() {
        int[] A = { 2, 2, 3, 3, 3, 3, 3, 3, 6 };
        int target = 3;
        int rs[] = searchRange(A, target);
        System.out.println(rs[0] + "\t" + rs[1]);
    }
}
